1include <../std.scad>
2
3
4//the commented lines are for tests to be written
5//the tests are ordered as they appear in geometry.scad
6
7
8
9test_is_point_on_line();
10test_is_collinear();
11test_point_line_distance();
12test_segment_distance();
13test_line_normal();
14test_line_intersection();
15//test_line_ray_intersection(); // should add this type of case
16//test_ray_intersection(); // should add this type of case
17//test_ray_segment_intersection(); // should add this type of case
18test_line_closest_point();
19//test_ray_closest_point(); // should add this type of case
20test_line_from_points();
21test_plane3pt();
22test_plane3pt_indexed();
23test_plane_from_normal();
24test_plane_from_points();
25test_plane_from_polygon();
26test_plane_normal();
27test_plane_offset();
28test_plane_closest_point();
29test_point_plane_distance();
30
31test__general_plane_line_intersection();
32test_plane_line_angle();
33test_plane_line_intersection();
34test_polygon_line_intersection();
35test_plane_intersection();
36test_is_coplanar();
37test_are_points_on_plane();
38test__is_point_above_plane();
39test_circle_2tangents();
40test_circle_3points();
41test_circle_point_tangents();
42
43test__noncollinear_triple();
44test_polygon_area();
45test_is_polygon_convex();
46test_reindex_polygon();
47test_align_polygon();
48test_centroid();
49test_point_in_polygon();
50test_polygon_triangulate();
51test_is_polygon_clockwise();
52test_clockwise_polygon();
53test_ccw_polygon();
54test_reverse_polygon();
55
56test_polygon_normal();
57test_rot_decode();
58
59//tests to migrate to other files
60test_convex_distance();
61test_convex_collision();
62
63// to be used when there are two alternative symmetrical outcomes
64// from a function like a plane output; v must be a vector
65function standardize(v) =
66 v==[]? [] :
67 let( i = max_index([for(vi=v) abs(vi) ]),
68 s = sign(v[i]) )
69 v*s;
70
71
72module assert_std(vc,ve,info) { assert_approx(standardize(vc),standardize(ve),info); }
73
74
75function info_str(list,i=0,string=chr(10)) =
76 assert(i>=len(list) || (is_list(list[i])&&len(list[i])>=2), "Invalid list for info_str." )
77 i>=len(list)
78 ? str(string)
79 : info_str(list,i+1,str(string,str(list[i][0],_valstr(list[i][1]),chr(10))));
80
81
82module test_polygon_triangulate() {
83 poly0 = [ [0,0,1], [10,0,2], [10,10,0] ];
84 poly1 = [ [-10,0,-10], [10,0,10], [0,10,0], [-10,0,-10], [-4,4,-4], [4,4,4], [0,2,0], [-4,4,-4] ];
85 poly2 = [ [0,0], [5,5], [-5,5], [0,0], [-5,-5], [5,-5] ];
86 poly3 = [ [0,0], [10,0], [10,10], [10,13], [10,10], [0,10], [0,0], [3,3], [7,3], [7,7], [7,3], [3,3] ];
87 tris0 = (polygon_triangulate(poly0));
88 assert(approx(tris0, [[0, 1, 2]]));
89 tris1 = (polygon_triangulate(poly1));
90 assert(approx(tris1,( [[2, 3, 4], [6, 7, 0], [2, 4, 5], [6, 0, 1], [1, 2, 5], [5, 6, 1]])));
91 tris2 = (polygon_triangulate(poly2));
92 assert(approx(tris2,( [[3, 4, 5], [1, 2, 3]])));
93 tris3 = (polygon_triangulate(poly3));
94 assert(approx(tris3,( [[5, 6, 7], [11, 0, 1], [5, 7, 8], [10, 11, 1], [5, 8, 9], [10, 1, 2], [4, 5, 9], [9, 10, 2]])));
95}
96
97module test__normalize_plane(){
98 plane = rands(-5,5,4,seed=333)+[10,0,0,0];
99 plane2 = _normalize_plane(plane);
100 assert_approx(norm(point3d(plane2)),1);
101 assert_approx(plane*plane2[3],plane2*plane[3]);
102}
103test__normalize_plane();
104
105module test_plane_line_intersection(){
106 line = [rands(-1,1,3,seed=74),rands(-1,1,3,seed=99)+[2,0,0]];
107 plane1 = plane_from_normal(line[1]-line[0],2*line[0]-line[1]); // plane disjoint from segment
108 plane2 = plane_from_normal(line[1]-line[0],(line[0]+line[1])/2); // through middle point of line
109 plane3 = plane3pt(line[1],line[0], rands(-1,1,3)+[0,3,0]); // containing line
110 plane4 = plane3pt(line[1],line[0], rands(-1,1,3)+[0,3,0])+[0,0,0,1]; // parallel to line
111 info1 = info_str([ ["line = ",line],["plane = ",plane1]]);
112 assert_approx(plane_line_intersection(plane1, line),2*line[0]-line[1],info1);
113 assert_approx(plane_line_intersection(plane1, line,[true,false]),undef,info1);
114 assert_approx(plane_line_intersection(plane1, line,[false,true]),2*line[0]-line[1],info1);
115 assert_approx(plane_line_intersection(plane1, line,[true, true]),undef,info1);
116 info2 = info_str([ ["line = ",line],["plane = ",plane2]]);
117 assert_approx(plane_line_intersection(plane2, line),(line[0]+line[1])/2,info2);
118 assert_approx(plane_line_intersection(plane2, line,[true,false]),(line[0]+line[1])/2,info2);
119 assert_approx(plane_line_intersection(plane2, line,[false,true]),(line[0]+line[1])/2,info2);
120 assert_approx(plane_line_intersection(plane2, line,[true, true]),(line[0]+line[1])/2,info2);
121 info3 = info_str([ ["line = ",line],["plane = ",plane3]]);
122 assert_approx(plane_line_intersection(plane3, line),line,info3);
123 assert_approx(plane_line_intersection(plane3, line,[true,false]),line,info3);
124 assert_approx(plane_line_intersection(plane3, line,[false,true]),line,info3);
125 assert_approx(plane_line_intersection(plane3, line,[true, true]),line,info3);
126 info4 = info_str([ ["line = ",line],["plane = ",plane4]]);
127 assert_approx(plane_line_intersection(plane4, line),undef,info4);
128 assert_approx(plane_line_intersection(plane4, line,[true,false]),undef,info4);
129 assert_approx(plane_line_intersection(plane4, line,[false,true]),undef,info4);
130 assert_approx(plane_line_intersection(plane4, line,[true, true]),undef,info4);
131}
132*test_plane_line_intersection();
133
134
135module test_plane_intersection(){
136 line = [ rands(-1,1,3), rands(-1,1,3)+[2,0,0] ]; // a valid line
137 pt0 = line[0]-[2,0,0]; // 2 points not on the line
138 pt1 = line[1]-[0,2,0];
139 plane01 = plane3pt(line[0],line[1],pt0);
140 plane02 = plane3pt(line[0],line[1],pt1);
141 plane03 = plane3pt(line[0],pt0,pt1);
142 info = info_str([["plane1 = ",plane01],["plane2 = ",plane02],["plane3 = ",plane03]]);
143 assert_approx(plane_intersection(plane01,plane02,plane03),line[0],info);
144 assert_approx(plane_intersection(plane01,2*plane01),undef,info);
145 lineInters = plane_intersection(plane01,plane02);
146 assert_approx(line_closest_point(lineInters,line[0]), line[0], info);
147 assert_approx(line_closest_point(lineInters,line[1]), line[1], info);
148}
149*test_plane_intersection();
150
151
152module test_plane_offset(){
153 plane = rands(-1,1,4)+[2,0,0,0]; // a valid plane
154 info = info_str([["plane = ",plane]]);
155 assert_approx(plane_offset(plane), _normalize_plane(plane)[3],info);
156 assert_approx(plane_offset([1,1,1,1]), 1/sqrt(3),info);
157}
158*test_plane_offset();
159
160module test_plane_from_polygon(){
161 poly1 = [ rands(-1,1,3), rands(-1,1,3)+[2,0,0], rands(-1,1,3)+[0,2,2] ];
162 poly2 = concat(poly1, [sum(poly1)/3] );
163 info = info_str([["poly1 = ",poly1],["poly2 = ",poly2]]);
164 assert_approx(plane_from_polygon(poly1),plane3pt(poly1[0],poly1[1],poly1[2]),info);
165 assert_approx(plane_from_polygon(poly2),plane3pt(poly1[0],poly1[1],poly1[2]),info);
166}
167*test_plane_from_polygon();
168
169module test_plane_from_normal(){
170 normal = rands(-1,1,3)+[2,0,0];
171 point = rands(-1,1,3);
172 displ = normal*point;
173 info = info_str([["normal = ",normal],["point = ",point],["displ = ",displ]]);
174 assert_approx(plane_from_normal(normal,point)*[each point,-1],0,info);
175 assert_approx(plane_from_normal([1,1,1],[1,2,3]),[0.57735026919,0.57735026919,0.57735026919,3.46410161514]);
176}
177*test_plane_from_normal();
178
179module test_plane_line_angle() {
180 angs = rands(0,360,3);
181 displ = rands(-1,1,1)[0];
182 info = info_str([["angs = ",angs],["displ = ",displ]]);
183 assert_approx(plane_line_angle([each rot(angs,p=[0,0,1]),displ],[[0,0,0],rot(angs,p=[0,0,1])]),90,info);
184 assert_approx(plane_line_angle([each rot(angs,p=[0,0,1]),displ],[[0,0,0],rot(angs,p=[0,1,1])]),45,info);
185 assert_approx(plane_line_angle([each rot(angs,p=[0,0,1]),0],[[0,0,0],rot(angs,p=[1,1,1])]),35.2643896828);
186}
187*test_plane_line_angle();
188
189module test__general_plane_line_intersection() {
190 CRLF = chr(10);
191 // general line
192 plane1 = rands(-1,1,4)+[2,0,0,0]; // a random valid plane (normal!=0)
193 line1 = [ rands(-1,1,3), rands(-1,1,3)+[2,0,0] ]; // a random valid line (line1[0]!=line1[1])
194 inters1 = _general_plane_line_intersection(plane1, line1);
195 info1 = info_str([["line = ",line1],["plane = ",plane1]]);
196 if(inters1==undef) { // parallel to the plane ?
197 assert_approx( point3d(plane1)*(line1[1]-line1[0]), 0, info1);
198 assert( point3d(plane1)*line1[0]== plane1[3], info1); // not on the plane
199 }
200 if( inters1[1]==undef) { // on the plane ?
201 assert_approx( point3d(plane1)*(line1[1]-line1[0]), 0, info1);
202 assert_approx(point3d(plane1)*line1[0],plane1[3], info1) ; // on the plane
203 }
204 else {
205 interspoint = line1[0]+inters1[1]*(line1[1]-line1[0]);
206 assert_approx(inters1[0],interspoint, info1);
207 assert_approx(point3d(plane1)*inters1[0], plane1[3], info1); // interspoint on the plane
208 assert_approx(point_plane_distance(plane1, inters1[0]), 0, info1); // inters1[0] on the plane
209 }
210
211 // line parallel to the plane
212 line2 = [ rands(-1,1,3)+[0,2,0], rands(-1,1,3)+[2,0,0] ]; // a random valid line2
213 // not containing the origin
214 plane0 = plane_from_points([line2[0], line2[1], [0,0,0]]); // plane cointaining the line
215 plane2 = plane_from_normal(plane_normal(plane0), [5,5,5]);
216 inters2 = _general_plane_line_intersection(plane2, line2);
217 info2 = info_str([["line = ",line2],["plane = ",plane2]]);
218 assert(inters2==undef, info2);
219
220 // line on the plane
221 line3 = [ rands(-1,1,3), rands(-1,1,3)+[2,0,0] ]; // a random valid line
222 imax = max_index(line3[1]-line3[0]);
223 w = [for(j=[0:2]) imax==j? 0: 3 ];
224 p3 = line3[0] + cross(line3[1]-line3[0],w); // a point not on the line
225 plane3 = plane_from_points([line3[0], line3[1], p3]); // plane containing line
226 inters3 = _general_plane_line_intersection(plane3, line3);
227 info3 = info_str([["line = ",line3],["plane = ",plane3]]);
228 assert(!is_undef(inters3) && inters3[1]==undef, info3);
229 assert_approx(inters3[0], line3, info3);
230}
231*test__general_plane_line_intersection();
232
233
234module test_are_points_on_plane() {
235 pts = [for(i=[0:40]) rands(-1,1,3) ];
236 dir = rands(-10,10,3);
237 normal0 = [1,2,3];
238 ang = rands(0,360,1)[0];
239 normal = rot(a=ang,p=normal0);
240 plane = [each normal, normal*dir];
241 prj_pts = plane_closest_point(plane,pts);
242 info = info_str([["pts = ",pts],["dir = ",dir],["ang = ",ang]]);
243 assert(are_points_on_plane(prj_pts,plane),info);
244 assert(!are_points_on_plane(concat(pts,[normal-dir]),plane),info);
245}
246*test_are_points_on_plane();
247
248module test_plane_closest_point(){
249 ang = rands(0,360,1)[0];
250 dir = rands(-10,10,3);
251 normal0 = unit([1,2,3]);
252 normal = rot(a=ang,p=normal0);
253 plane0 = [each normal0, 0];
254 plane = [each normal, 0];
255 planem = [each normal, normal*dir];
256 pts = [for(i=[1:10]) rands(-1,1,3)];
257 info = info_str([["ang = ",ang],["dir = ",dir]]);
258 assert_approx( plane_closest_point(plane,pts),
259 plane_closest_point(plane,plane_closest_point(plane,pts)),info);
260 assert_approx( plane_closest_point(plane,pts),
261 rot(a=ang,p=plane_closest_point(plane0,rot(a=-ang,p=pts))),info);
262 assert_approx( move((-normal*dir)*normal,p=plane_closest_point(planem,pts)),
263 plane_closest_point(plane,pts),info);
264 assert_approx( move((normal*dir)*normal,p=plane_closest_point(plane,pts)),
265 plane_closest_point(planem,pts),info);
266}
267*test_plane_closest_point();
268
269module test_line_from_points() {
270 assert_approx(line_from_points([[1,0],[0,0],[-1,0]]),[[-1,0],[1,0]]);
271 assert_approx(line_from_points([[1,1],[0,1],[-1,1]]),[[-1,1],[1,1]]);
272 assert(line_from_points([[1,1],[0,1],[-1,0]])==undef);
273 assert(line_from_points([[1,1],[0,1],[-1,0]],fast=true)== [[-1,0],[1,1]]);
274}
275*test_line_from_points();
276
277module test_is_point_on_line() {
278 assert(is_point_on_line([-15,0], [[-10,0], [10,0]],SEGMENT) == false);
279 assert(is_point_on_line([-10,0], [[-10,0], [10,0]],SEGMENT) == true);
280 assert(is_point_on_line([-5,0], [[-10,0], [10,0]],SEGMENT) == true);
281 assert(is_point_on_line([0,0], [[-10,0], [10,0]],SEGMENT) == true);
282 assert(is_point_on_line([3,3], [[-10,0], [10,0]],SEGMENT) == false);
283 assert(is_point_on_line([5,0], [[-10,0], [10,0]],SEGMENT) == true);
284 assert(is_point_on_line([10,0], [[-10,0], [10,0]],SEGMENT) == true);
285 assert(is_point_on_line([15,0], [[-10,0], [10,0]],SEGMENT) == false);
286
287 assert(is_point_on_line([0,-15], [[0,-10], [0,10]],SEGMENT) == false);
288 assert(is_point_on_line([0,-10], [[0,-10], [0,10]],SEGMENT) == true);
289 assert(is_point_on_line([0, -5], [[0,-10], [0,10]],SEGMENT) == true);
290 assert(is_point_on_line([0, 0], [[0,-10], [0,10]],SEGMENT) == true);
291 assert(is_point_on_line([3, 3], [[0,-10], [0,10]],SEGMENT) == false);
292 assert(is_point_on_line([0, 5], [[0,-10], [0,10]],SEGMENT) == true);
293 assert(is_point_on_line([0, 10], [[0,-10], [0,10]],SEGMENT) == true);
294 assert(is_point_on_line([0, 15], [[0,-10], [0,10]],SEGMENT) == false);
295
296 assert(is_point_on_line([-15,-15], [[-10,-10], [10,10]],SEGMENT) == false);
297 assert(is_point_on_line([-10,-10], [[-10,-10], [10,10]],SEGMENT) == true);
298 assert(is_point_on_line([ -5, -5], [[-10,-10], [10,10]],SEGMENT) == true);
299 assert(is_point_on_line([ 0, 0], [[-10,-10], [10,10]],SEGMENT) == true);
300 assert(is_point_on_line([ 0, 3], [[-10,-10], [10,10]],SEGMENT) == false);
301 assert(is_point_on_line([ 5, 5], [[-10,-10], [10,10]],SEGMENT) == true);
302 assert(is_point_on_line([ 10, 10], [[-10,-10], [10,10]],SEGMENT) == true);
303 assert(is_point_on_line([ 15, 15], [[-10,-10], [10,10]],SEGMENT) == false);
304
305 assert(is_point_on_line([10,10], [[0,0],[5,5]]) == true);
306 assert(is_point_on_line([4,4], [[0,0],[5,5]]) == true);
307 assert(is_point_on_line([-2,-2], [[0,0],[5,5]]) == true);
308 assert(is_point_on_line([5,5], [[0,0],[5,5]]) == true);
309 assert(is_point_on_line([10,10], [[0,0],[5,5]],RAY) == true);
310 assert(is_point_on_line([0,0], [[0,0],[5,5]],RAY) == true);
311 assert(is_point_on_line([3,3], [[0,0],[5,5]],RAY) == true);
312}
313*test_is_point_on_line();
314
315
316module test__point_left_of_line2d() {
317 assert(_point_left_of_line2d([ -3, 0], [[-10,-10], [10,10]]) > 0);
318 assert(_point_left_of_line2d([ 0, 0], [[-10,-10], [10,10]]) == 0);
319 assert(_point_left_of_line2d([ 3, 0], [[-10,-10], [10,10]]) < 0);
320}
321test__point_left_of_line2d();
322
323module test_is_collinear() {
324 assert(is_collinear([-10,-10], [-15, -16], [10,10]) == false);
325 assert(is_collinear([[-10,-10], [-15, -16], [10,10]]) == false);
326 assert(is_collinear([-10,-10], [-15, -15], [10,10]) == true);
327 assert(is_collinear([[-10,-10], [-15, -15], [10,10]]) == true);
328 assert(is_collinear([-10,-10], [ -3, 0], [10,10]) == false);
329 assert(is_collinear([-10,-10], [ 0, 0], [10,10]) == true);
330 assert(is_collinear([-10,-10], [ 3, 0], [10,10]) == false);
331 assert(is_collinear([-10,-10], [ 15, 15], [10,10]) == true);
332 assert(is_collinear([-10,-10], [ 15, 16], [10,10]) == false);
333}
334*test_is_collinear();
335
336
337module test_point_line_distance() {
338 assert_approx(point_line_distance([1,1,1], [[-10,-10,-10], [10,10,10]]), 0);
339 assert_approx(point_line_distance([-1,-1,-1], [[-10,-10,-10], [10,10,10]]), 0);
340 assert_approx(point_line_distance([1,-1,0], [[-10,-10,-10], [10,10,10]]), sqrt(2));
341 assert_approx(point_line_distance([8,-8,0], [[-10,-10,-10], [10,10,10]]), 8*sqrt(2));
342 assert_approx(point_line_distance([3,8], [[-10,0], [10,0]],SEGMENT), 8);
343 assert_approx(point_line_distance([14,3], [[-10,0], [10,0]],SEGMENT), 5);
344}
345*test_point_line_distance();
346
347
348module test_segment_distance() {
349 assert_approx(segment_distance([[-14,3], [-14,9]], [[-10,0], [10,0]]), 5);
350 assert_approx(segment_distance([[-14,3], [-15,9]], [[-10,0], [10,0]]), 5);
351 assert_approx(segment_distance([[14,3], [14,9]], [[-10,0], [10,0]]), 5);
352 assert_approx(segment_distance([[-14,-3], [-14,-9]], [[-10,0], [10,0]]), 5);
353 assert_approx(segment_distance([[-14,-3], [-15,-9]], [[-10,0], [10,0]]), 5);
354 assert_approx(segment_distance([[14,-3], [14,-9]], [[-10,0], [10,0]]), 5);
355 assert_approx(segment_distance([[14,3], [14,-3]], [[-10,0], [10,0]]), 4);
356 assert_approx(segment_distance([[-14,3], [-14,-3]], [[-10,0], [10,0]]), 4);
357 assert_approx(segment_distance([[-6,5], [4,-5]], [[-10,0], [10,0]]), 0);
358 assert_approx(segment_distance([[-5,5], [5,-5]], [[-10,3], [10,-3]]), 0);
359}
360*test_segment_distance();
361
362
363module test_line_normal() {
364 assert(line_normal([0,0],[10,0]) == [0,1]);
365 assert(line_normal([0,0],[0,10]) == [-1,0]);
366 assert(line_normal([0,0],[-10,0]) == [0,-1]);
367 assert(line_normal([0,0],[0,-10]) == [1,0]);
368 assert(approx(line_normal([0,0],[10,10]), [-sqrt(2)/2,sqrt(2)/2]));
369 assert(line_normal([[0,0],[10,0]]) == [0,1]);
370 assert(line_normal([[0,0],[0,10]]) == [-1,0]);
371 assert(line_normal([[0,0],[-10,0]]) == [0,-1]);
372 assert(line_normal([[0,0],[0,-10]]) == [1,0]);
373 assert(approx(line_normal([[0,0],[10,10]]), [-sqrt(2)/2,sqrt(2)/2]));
374 pts = [for (p=pair(rands(-100,100,1000,seed_value=4312))) p];
375 for (p = pair(pts,true)) {
376 p1 = p.x;
377 p2 = p.y;
378 n = unit(p2-p1);
379 n1 = [-n.y, n.x];
380 n2 = line_normal(p1,p2);
381 assert(approx(n2, n1));
382 }
383}
384*test_line_normal();
385
386
387module test_line_intersection() {
388 assert(line_intersection([[-10,-10], [ -1,-10]], [[ 10,-10], [ 1,-10]]) == undef);
389 assert(line_intersection([[-10, 0], [ -1, 0]], [[ 10, 0], [ 1, 0]]) == undef);
390 assert(line_intersection([[-10, 0], [ -1, 0]], [[ 1, 0], [ 10, 0]]) == undef);
391 assert(line_intersection([[-10, 0], [ 10, 0]], [[-10, 0], [ 10, 0]]) == undef);
392 assert(line_intersection([[-10, 10], [ 10, 10]], [[-10,-10], [ 10,-10]]) == undef);
393 assert(line_intersection([[-10,-10], [ -1, -1]], [[ 10,-10], [ 1, -1]]) == [0,0]);
394 assert(line_intersection([[-10,-10], [ 10, 10]], [[ 10,-10], [-10, 10]]) == [0,0]);
395 assert(line_intersection([[ -8, 0], [ 12, 4]], [[ 12, 0], [ -8, 4]]) == [2,2]);
396 assert(line_intersection([[-10,-10], [ -1,-10]], [[ 10,-10], [ 1,-10]],LINE,SEGMENT) == undef);
397 assert(line_intersection([[-10, 0], [ -1, 0]], [[ 10, 0], [ 1, 0]],LINE,SEGMENT) == undef);
398 assert(line_intersection([[-10, 0], [ -1, 0]], [[ 1, 0], [ 10, 0]],LINE,SEGMENT) == undef);
399 assert(line_intersection([[-10, 0], [ 10, 0]], [[-10, 0], [ 10, 0]],LINE,SEGMENT) == undef);
400 assert(line_intersection([[-10, 10], [ 10, 10]], [[-10,-10], [ 10,-10]],LINE,SEGMENT) == undef);
401 assert(line_intersection([[-10,-10], [ -1, -1]], [[ 10,-10], [ 1, -1]],LINE,SEGMENT) == undef);
402 assert(line_intersection([[-10,-10], [ 10, 10]], [[ 10,-10], [-10, 10]],LINE,SEGMENT) == [0,0]);
403 assert(line_intersection([[ -8, 0], [ 12, 4]], [[ 12, 0], [ -8, 4]],LINE,SEGMENT) == [2,2]);
404 assert(line_intersection([[-10,-10], [ 10, 10]], [[ 10,-10], [ 1, -1]],LINE,SEGMENT) == undef);
405 assert(line_intersection([[-10,-10], [ 10, 10]], [[ 10,-10], [ -1, 1]],LINE,SEGMENT) == [0,0]);
406}
407*test_line_intersection();
408
409
410module test_line_closest_point() {
411 assert(approx(line_closest_point([[-10,-10], [10,10]], [1,-1]), [0,0]));
412 assert(approx(line_closest_point([[-10,-10], [10,10]], [-1,1]), [0,0]));
413 assert(approx(line_closest_point([[-10,-20], [10,20]], [1,2]+[-2,1]), [1,2]));
414 assert(approx(line_closest_point([[-10,-20], [10,20]], [1,2]+[2,-1]), [1,2]));
415 assert(approx(line_closest_point([[-10,-20], [10,20]], [13,31]), [15,30]));
416 assert(approx(line_closest_point([[-10,-10], [10,10]], [1,-1],SEGMENT), [0,0]));
417 assert(approx(line_closest_point([[-10,-10], [10,10]], [-1,1],SEGMENT), [0,0]));
418 assert(approx(line_closest_point([[-10,-20], [10,20]], [1,2]+[-2,1],SEGMENT), [1,2]));
419 assert(approx(line_closest_point([[-10,-20], [10,20]], [1,2]+[2,-1],SEGMENT), [1,2]));
420 assert(approx(line_closest_point([[-10,-20], [10,20]], [13,31],SEGMENT), [10,20]));
421 assert(approx(line_closest_point([[-10,-20], [10,20]], [15,25],SEGMENT), [10,20]));
422}
423*test_line_closest_point();
424
425module test_circle_2tangents() {
426//** missing tests with arg tangent=true
427 assert(approx(circle_2tangents(10/sqrt(2),[10,10],[0,0],[10,-10])[0], [10,0]));
428 assert(approx(circle_2tangents(10/sqrt(2),[-10,10],[0,0],[-10,-10])[0], [-10,0]));
429 assert(approx(circle_2tangents(10/sqrt(2),[-10,10],[0,0],[10,10])[0], [0,10]));
430 assert(approx(circle_2tangents(10/sqrt(2),[-10,-10],[0,0],[10,-10])[0], [0,-10]));
431 assert(approx(circle_2tangents(10,[0,10],[0,0],[10,0])[0], [10,10]));
432 assert(approx(circle_2tangents(10,[10,0],[0,0],[0,-10])[0], [10,-10]));
433 assert(approx(circle_2tangents(10,[0,-10],[0,0],[-10,0])[0], [-10,-10]));
434 assert(approx(circle_2tangents(10,[-10,0],[0,0],[0,10])[0], [-10,10]));
435 assert_approx(circle_2tangents(10,polar_to_xy(10,60),[0,0],[10,0])[0], polar_to_xy(20,30));
436}
437*test_circle_2tangents();
438
439
440module test_circle_3points() {
441 count = 200;
442 coords = rands(-100,100,count,seed_value=888);
443 radii = rands(10,100,count,seed_value=390);
444 angles = rands(0,360,count,seed_value=699);
445 // 2D tests.
446 for(i = count(count)) {
447 cp = select(coords,i,i+1);
448 r = radii[i];
449 angs = sort(select(angles,i,i+2));
450 pts = [for (a=angs) cp+polar_to_xy(r,a)];
451 res = circle_3points(pts);
452 if (!approx(res[0], cp)) {
453 echo(cp=cp, r=r, angs=angs);
454 echo(pts=pts);
455 echo(got=res[0], expected=cp, delta=res[0]-cp);
456 assert(approx(res[0], cp));
457 }
458 if (!approx(res[1], r)) {
459 echo(cp=cp, r=r, angs=angs);
460 echo(pts=pts);
461 echo(got=res[1], expected=r, delta=res[1]-r);
462 assert(approx(res[1], r));
463 }
464 if (!approx(res[2], UP)) {
465 echo(cp=cp, r=r, angs=angs);
466 echo(pts=pts);
467 echo(got=res[2], expected=UP, delta=res[2]-UP);
468 assert(approx(res[2], UP));
469 }
470 }
471 for(i = count(count)) {
472 cp = select(coords,i,i+1);
473 r = radii[i];
474 angs = sort(select(angles,i,i+2));
475 pts = [for (a=angs) cp+polar_to_xy(r,a)];
476 res = circle_3points(pts[0], pts[1], pts[2]);
477 if (!approx(res[0], cp)) {
478 echo(cp=cp, r=r, angs=angs);
479 echo(pts=pts);
480 echo(got=res[0], expected=cp, delta=res[0]-cp);
481 assert(approx(res[0], cp));
482 }
483 if (!approx(res[1], r)) {
484 echo(cp=cp, r=r, angs=angs);
485 echo(pts=pts);
486 echo(got=res[1], expected=r, delta=res[1]-r);
487 assert(approx(res[1], r));
488 }
489 if (!approx(res[2], UP)) {
490 echo(cp=cp, r=r, angs=angs);
491 echo(pts=pts);
492 echo(got=res[2], expected=UP, delta=res[2]-UP);
493 assert(approx(res[2], UP));
494 }
495 }
496 // 3D tests.
497 for(i = count(count)) {
498 cp = select(coords,i,i+2);
499 r = radii[i];
500 nrm = unit(select(coords,i+10,i+12));
501 n = nrm.z<0? -nrm : nrm;
502 angs = sort(select(angles,i,i+2));
503 pts = translate(cp,p=rot(from=UP,to=n,p=[for (a=angs) point3d(polar_to_xy(r,a))]));
504 res = circle_3points(pts);
505 if (!approx(res[0], cp)) {
506 echo(cp=cp, r=r, angs=angs, n=n);
507 echo(pts=pts);
508 echo("CP:", got=res[0], expected=cp, delta=res[0]-cp);
509 assert(approx(res[0], cp));
510 }
511 if (!approx(res[1], r)) {
512 echo(cp=cp, r=r, angs=angs, n=n);
513 echo(pts=pts);
514 echo("R:", got=res[1], expected=r, delta=res[1]-r);
515 assert(approx(res[1], r));
516 }
517 if (!approx(res[2], n)) {
518 echo(cp=cp, r=r, angs=angs, n=n);
519 echo(pts=pts);
520 echo("NORMAL:", got=res[2], expected=n, delta=res[2]-n);
521 assert(approx(res[2], n));
522 }
523 }
524 for(i = count(count)) {
525 cp = select(coords,i,i+2);
526 r = radii[i];
527 nrm = unit(select(coords,i+10,i+12));
528 n = nrm.z<0? -nrm : nrm;
529 angs = sort(select(angles,i,i+2));
530 pts = translate(cp,p=rot(from=UP,to=n,p=[for (a=angs) point3d(polar_to_xy(r,a))]));
531 res = circle_3points(pts[0], pts[1], pts[2]);
532 if (!approx(res[0], cp)) {
533 echo(cp=cp, r=r, angs=angs, n=n);
534 echo(pts=pts);
535 echo("CENTER:", got=res[0], expected=cp, delta=res[0]-cp);
536 assert(approx(res[0], cp));
537 }
538 if (!approx(res[1], r)) {
539 echo(cp=cp, r=r, angs=angs, n=n);
540 echo(pts=pts);
541 echo("RADIUS:", got=res[1], expected=r, delta=res[1]-r);
542 assert(approx(res[1], r));
543 }
544 if (!approx(res[2], n)) {
545 echo(cp=cp, r=r, angs=angs, n=n);
546 echo(pts=pts);
547 echo("NORMAL:", got=res[2], expected=n, delta=res[2]-n);
548 assert(approx(res[2], n));
549 }
550 }
551}
552*test_circle_3points();
553
554
555module test_circle_point_tangents() {
556 testvals = [
557 // cp r pt expect
558 [[0,0], 50, [50*sqrt(2),0], [polar_to_xy(50,45), polar_to_xy(50,-45)]],
559 [[5,10], 50, [5+50*sqrt(2),10], [[5,10]+polar_to_xy(50,45), [5,10]+polar_to_xy(50,-45)]],
560 [[0,0], 50, [0,50*sqrt(2)], [polar_to_xy(50,135), polar_to_xy(50,45)]],
561 [[5,10], 50, [5,10+50*sqrt(2)], [[5,10]+polar_to_xy(50,135), [5,10]+polar_to_xy(50,45)]],
562 [[5,10], 50, [5,10+50*sqrt(2)], [[5,10]+polar_to_xy(50,135), [5,10]+polar_to_xy(50,45)]],
563 [[5,10], 50, [5, 60], [[5, 60]]],
564 [[5,10], 50, [5, 59], []],
565 ];
566 for (v = testvals) {
567 cp = v[0]; r = v[1]; pt = v[2]; expect = v[3];
568 info = str("cp=",cp, ", r=",r, ", pt=",pt);
569 assert_approx(circle_point_tangents(r=r,cp=cp,pt=pt), expect, info);
570 }
571}
572*test_circle_point_tangents();
573
574
575module test_plane3pt() {
576 assert_approx(plane3pt([0,0,20], [0,10,10], [0,0,0]), [1,0,0,0]);
577 assert_approx(plane3pt([2,0,20], [2,10,10], [2,0,0]), [1,0,0,2]);
578 assert_approx(plane3pt([0,0,0], [10,0,10], [0,0,20]), [0,1,0,0]);
579 assert_approx(plane3pt([0,2,0], [10,2,10], [0,2,20]), [0,1,0,2]);
580 assert_approx(plane3pt([0,0,0], [10,10,0], [20,0,0]), [0,0,1,0]);
581 assert_approx(plane3pt([0,0,2], [10,10,2], [20,0,2]), [0,0,1,2]);
582}
583*test_plane3pt();
584
585module test_plane3pt_indexed() {
586 pts = [ [0,0,0], [10,0,0], [0,10,0], [0,0,10] ];
587 s13 = sqrt(1/3);
588 assert_approx(plane3pt_indexed(pts, 0,3,2), [1,0,0,0]);
589 assert_approx(plane3pt_indexed(pts, 0,2,3), [-1,0,0,0]);
590 assert_approx(plane3pt_indexed(pts, 0,1,3), [0,1,0,0]);
591 assert_approx(plane3pt_indexed(pts, 0,3,1), [0,-1,0,0]);
592 assert_approx(plane3pt_indexed(pts, 0,2,1), [0,0,1,0]);
593 assert_approx(plane3pt_indexed(pts, 0,1,2), [0,0,-1,0]);
594 assert_approx(plane3pt_indexed(pts, 3,2,1), [s13,s13,s13,10*s13]);
595 assert_approx(plane3pt_indexed(pts, 1,2,3), [-s13,-s13,-s13,-10*s13]);
596}
597*test_plane3pt_indexed();
598
599module test_plane_from_points() {
600 assert_std(plane_from_points([[0,0,20], [0,10,10], [0,0,0], [0,5,3]]), [1,0,0,0]);
601 assert_std(plane_from_points([[2,0,20], [2,10,10], [2,0,0], [2,3,4]]), [1,0,0,2]);
602 assert_std(plane_from_points([[0,0,0], [10,0,10], [0,0,20], [5,0,7]]), [0,1,0,0]);
603 assert_std(plane_from_points([[0,2,0], [10,2,10], [0,2,20], [4,2,3]]), [0,1,0,2]);
604 assert_std(plane_from_points([[0,0,0], [10,10,0], [20,0,0], [8,3,0]]), [0,0,1,0]);
605 assert_std(plane_from_points([[0,0,2], [10,10,2], [20,0,2], [3,4,2]]), [0,0,1,2]);
606}
607*test_plane_from_points();
608
609
610module test_polygon_normal() {
611 circ = path3d(circle($fn=37, r=3));
612
613 assert_approx(polygon_normal(circ), UP);
614 assert_approx(polygon_normal(rot(from=UP,to=[1,2,3],p=circ)), unit([1,2,3]));
615 assert_approx(polygon_normal(rot(from=UP,to=[4,-2,3],p=reverse(circ))), -unit([4,-2,3]));
616 assert_approx(polygon_normal(path3d([[0,0], [10,10], [11,10], [0,-1], [-1,1]])), UP);
617}
618*test_polygon_normal();
619
620module test_plane_normal() {
621 assert_approx(plane_normal(plane3pt([0,0,20], [0,10,10], [0,0,0])), [1,0,0]);
622 assert_approx(plane_normal(plane3pt([2,0,20], [2,10,10], [2,0,0])), [1,0,0]);
623 assert_approx(plane_normal(plane3pt([0,0,0], [10,0,10], [0,0,20])), [0,1,0]);
624 assert_approx(plane_normal(plane3pt([0,2,0], [10,2,10], [0,2,20])), [0,1,0]);
625 assert_approx(plane_normal(plane3pt([0,0,0], [10,10,0], [20,0,0])), [0,0,1]);
626 assert_approx(plane_normal(plane3pt([0,0,2], [10,10,2], [20,0,2])), [0,0,1]);
627}
628*test_plane_normal();
629
630
631module test_point_plane_distance() {
632 plane1 = plane3pt([-10,0,0], [0,10,0], [10,0,0]);
633 assert(point_plane_distance(plane1, [0,0,5]) == 5);
634 assert(point_plane_distance(plane1, [5,5,8]) == 8);
635}
636*test_point_plane_distance();
637
638
639module test_polygon_line_intersection() {
640 poly0 = [ [-10,-10, 0],[10,-10, 0],[10,10,0],[0,5,0],[-10,10,0] ];
641 line0 = [ [-3,7.5,0],[3,7.5,0] ]; // a segment on poly0 plane, out of poly0
642 angs = rands(0,360,3);
643 poly = rot(angs,p=poly0);
644 lineon = rot(angs,p=line0);
645 info = info_str([["angs = ",angs],["line = ",lineon],["poly = ",poly]]);
646 // line on polygon plane
647 assert_approx(polygon_line_intersection(poly,lineon,bounded=[true,true]),
648 undef, info);
649 assert_approx(polygon_line_intersection(poly,lineon,bounded=[true,false]),
650 [rot(angs,p=[[5,7.5,0],[10,7.5,0]])], info);
651 assert_approx(polygon_line_intersection(poly,lineon,bounded=[false,true]),
652 [rot(angs,p=[[-10,7.5,0],[-5,7.5,0]])], info);
653 assert_approx(polygon_line_intersection(poly,lineon,bounded=[false,false]),
654 rot(angs,p=[[[-10,7.5,0],[-5,7.5,0]],[[5,7.5,0],[10,7.5,0]]]), info);
655 // line parallel to polygon plane
656 linepll = move([0,0,1],lineon);
657 assert_approx(polygon_line_intersection(poly,linepll,bounded=[true,true]),
658 undef, info);
659 assert_approx(polygon_line_intersection(poly,linepll,bounded=[true,false]),
660 undef, info);
661 assert_approx(polygon_line_intersection(poly,linepll,bounded=[false,true]),
662 undef, info);
663 assert_approx(polygon_line_intersection(poly,linepll,bounded=[false,false]),
664 undef, info);
665 // general case
666 trnsl = [0,0,1];
667 linegnr = move(trnsl,rot(angs,p=[[5,5,5],[3,3,3]]));
668 polygnr = move(trnsl,rot(angs,p=poly0));
669 assert_approx(polygon_line_intersection(polygnr,linegnr,bounded=[true,true]),
670 undef, info);
671 assert_approx(polygon_line_intersection(polygnr,linegnr,bounded=[true,false]),
672 trnsl, info);
673 assert_approx(polygon_line_intersection(polygnr,linegnr,bounded=[false,true]),
674 undef, info);
675 assert_approx(polygon_line_intersection(polygnr,linegnr,bounded=[false,false]),
676 trnsl, info);
677
678 sq = path3d(square(10));
679 pentagram = 10*path3d(turtle(["move",10,"left",144], repeat=4));
680 for (tran = [ident(4), skew(sxy=1.2)*scale([.9,1,1.2])*yrot(14)*zrot(37)*xrot(9)])
681 {
682 assert_approx(polygon_line_intersection(apply(tran,sq),apply(tran,[[5,5,-1], [5,5,10]])), apply(tran, [5,5,0]));
683 assert_approx(polygon_line_intersection(apply(tran,sq),apply(tran,[[5,5,1], [5,5,10]])), apply(tran, [5,5,0]));
684 assert(undef==polygon_line_intersection(apply(tran,sq),apply(tran,[[5,5,1], [5,5,10]]),RAY));
685 assert(undef==polygon_line_intersection(apply(tran,sq),apply(tran,[[11,11,-1],[11,11,1]])));
686 assert_approx(polygon_line_intersection(apply(tran,sq),apply(tran,[[5,0,-10], [5,0,10]])), apply(tran, [5,0,0]));
687 assert_equal(polygon_line_intersection(apply(tran,sq),apply(tran,[[5,0,1], [5,0,10]]),RAY), undef);
688 assert_approx(polygon_line_intersection(apply(tran,sq),apply(tran,[[10,0,1],[10,0,10]])), apply(tran, [10,0,0]));
689 assert_approx(polygon_line_intersection(apply(tran,sq),apply(tran,[[1,5,0],[9,6,0]])), apply(tran, [[[0,4.875,0],[10,6.125,0]]]));
690 assert_approx(polygon_line_intersection(apply(tran,sq),apply(tran,[[1,5,0],[9,6,0]]),SEGMENT), apply(tran, [[[1,5,0],[9,6,0]]]));
691 assert_approx(polygon_line_intersection(apply(tran,sq),apply(tran,[[-1,-1,0],[8,8,0]])), apply(tran, [[[0,0,0],[10,10,0]]]));
692 assert_approx(polygon_line_intersection(apply(tran,sq),apply(tran,[[-1,-1,0],[8,8,0]]),SEGMENT), apply(tran, [[[0,0,0],[8,8,0]]]));
693 assert_approx(polygon_line_intersection(apply(tran,sq),apply(tran,[[-1,-1,0],[8,8,0]]),RAY), apply(tran, [[[0,0,0],[10,10,0]]]));
694 assert_approx(polygon_line_intersection(apply(tran,sq),apply(tran,[[-2,4,0], [12,11,0]]),RAY), apply(tran, [[[0,5,0],[10,10,0]]]));
695 assert_equal(polygon_line_intersection(apply(tran,sq),apply(tran,[[-20,0,0],[20,40,0]]),RAY), undef);
696 assert_approx(polygon_line_intersection(apply(tran,sq),apply(tran,[[-1,0,0],[11,0,0]])), apply(tran, [[[0,0,0],[10,0,0]]]));
697 }
698 assert_approx(polygon_line_intersection(path2d(sq),[[1,5],[9,6]],SEGMENT), [[[1,5],[9,6]]]);
699 assert_approx(polygon_line_intersection(path2d(sq),[[1,5],[9,6]],LINE), [[[0,4.875],[10,6.125]]]);
700 assert_approx(polygon_line_intersection(pentagram,[[50,10,-4],[54,12,4]], nonzero=true), [52,11,0]);
701 assert_equal(polygon_line_intersection(pentagram,[[50,10,-4],[54,12,4]], nonzero=false), undef);
702 assert_approx(polygon_line_intersection(pentagram,[[50,-10,-4],[54,-12,4]], nonzero=true), [52,-11,0]);
703 assert_approx(polygon_line_intersection(pentagram,[[50,-10,-4],[54,-12,4]], nonzero=false), [52,-11,0]);
704 assert_approx(polygon_line_intersection(star(8,step=3,od=10), [[-5,3], [5,3]]),
705 [[[-3.31370849898, 3], [-2.24264068712, 3]],
706 [[-0.828427124746, 3], [0.828427124746, 3]],
707 [[2.24264068712, 3], [3.31370849898, 3]]]);
708
709 tran = skew(sxy=1.2)*scale([.9,1,1.2])*yrot(14)*zrot(37)*xrot(9);
710
711 // assemble multiple edges into one edge
712 assert_approx(polygon_line_intersection(star(r=15,n=8,step=2), [[20,-5],[-5,20]]), [[[15,0],[0,15]]]);
713 assert_approx(polygon_line_intersection(apply(tran,path3d(star(r=15,n=8,step=2))), apply(tran,[[20,-5,0],[-5,20,0]])), apply(tran,[[[15,0,0],[0,15,0]]]));
714 // line going the other direction
715 assert_approx(polygon_line_intersection(star(r=15,n=8,step=2), [[-5,20],[20,-5]]), [[[0,15],[15,0]]]);
716 assert_approx(polygon_line_intersection(apply(tran,path3d(star(r=15,n=8,step=2))), apply(tran,[[-5,20,0],[20,-5,0]])),apply(tran, [[[0,15,0],[15,0,0]]]));
717 // single point
718 assert_approx(polygon_line_intersection(hexagon(r=15), [[15,-10],[15,13]], RAY), [[[15,0]]]);
719 assert_approx(polygon_line_intersection(apply(tran,path3d(hexagon(r=15))), apply(tran,[[15,-10,0],[15,13,0]]), RAY),
720 [[apply(tran,[15,0,0])]]);
721 // two points
722 assert_approx(polygon_line_intersection(star(r=15,n=8,step=3), rot(22.5,p=[[15,-10],[15,20]],cp=[15,0])),
723 [[[15,0]], [[10.6066017178, 10.6066017178]]]);
724 assert_approx(polygon_line_intersection(apply(tran,path3d(star(r=15,n=8,step=3))), apply(tran,rot(22.5,p=[[15,-10,0],[15,20,0]],cp=[15,0,0]))),
725 [[apply(tran,[15,0,0])], [apply(tran,[10.6066017178, 10.6066017178,0])]]);
726 // two segments and one point
727 star7 = star(r=25,ir=9,n=7);
728 assert_approx(polygon_line_intersection(star7, [left(10,p=star7[8]), right(50,p=star7[8])]),
729 [[[-22.5242216976, 10.8470934779]],
730 [[-5.60077322195, 10.8470934779], [0.997372374838, 10.8470934779]],
731 [[4.61675816681, 10.8470934779], [11.4280421589, 10.8470934779]]]);
732 assert_approx(polygon_line_intersection(apply(tran,path3d(star7)),
733 apply(tran, path3d([left(10,p=star7[8]), right(50,p=star7[8])]))),
734 [[apply(tran,[-22.5242216976, 10.8470934779,0])],
735 apply(tran,[[-5.60077322195, 10.8470934779,0], [0.997372374838, 10.8470934779,0]]),
736 apply(tran,[[4.61675816681, 10.8470934779,0], [11.4280421589, 10.8470934779,0]])]);
737}
738*test_polygon_line_intersection();
739
740
741module test_is_coplanar() {
742 assert(is_coplanar([ [5,5,1],[0,0,1],[-1,-1,1] ]) == false);
743 assert(is_coplanar([ [5,5,1],[0,0,0],[-1,-1,1] ]) == true);
744 assert(is_coplanar([ [0,0,0],[1,0,1],[1,1,1], [0,1,2] ]) == false);
745 assert(is_coplanar([ [0,0,0],[1,0,1],[1,1,2], [0,1,1] ]) == true);
746 }
747*test_is_coplanar();
748
749
750module test__is_point_above_plane() {
751 plane = plane3pt([0,0,0], [0,10,10], [10,0,10]);
752 assert(_is_point_above_plane(plane, [5,5,10]) == false);
753 assert(_is_point_above_plane(plane, [-5,0,0]) == true);
754 assert(_is_point_above_plane(plane, [5,0,0]) == false);
755 assert(_is_point_above_plane(plane, [0,-5,0]) == true);
756 assert(_is_point_above_plane(plane, [0,5,0]) == false);
757 assert(_is_point_above_plane(plane, [0,0,5]) == true);
758 assert(_is_point_above_plane(plane, [0,0,-5]) == false);
759}
760*test__is_point_above_plane();
761
762
763
764
765module test_polygon_area() {
766 assert(approx(polygon_area([[1,1],[-1,1],[-1,-1],[1,-1]]), 4));
767 assert(approx(polygon_area(circle(r=50,$fn=1000),signed=true), -PI*50*50, eps=0.1));
768 assert(approx(polygon_area(rot([13,27,75],
769 p=path3d(circle(r=50,$fn=1000),fill=23)),
770 signed=true), PI*50*50, eps=0.1));
771 assert(abs(polygon_area([[0,0], [0,10], [10,0]],signed=true) + 50) < EPSILON);
772 assert(abs(polygon_area([[0,0], [0,10], [0,15]],signed=true)) < EPSILON);
773 assert(abs(polygon_area([[0,0], [10,0], [0,10]],signed=true) - 50) < EPSILON);
774}
775*test_polygon_area();
776
777
778module test_is_polygon_convex() {
779 assert(is_polygon_convex([[1,1],[-1,1],[-1,-1],[1,-1]]));
780 assert(is_polygon_convex(circle(r=50,$fn=1000)));
781 assert(is_polygon_convex(rot([50,120,30], p=path3d(circle(1,$fn=50)))));
782 assert(!is_polygon_convex([[1,1],[0,0],[-1,1],[-1,-1],[1,-1]]));
783 assert(!is_polygon_convex([for (i=[0:36]) let(a=-i*10) (10+i)*[cos(a),sin(a)]])); // spiral
784}
785*test_is_polygon_convex();
786
787
788module test_reindex_polygon() {
789 pent = subdivide_path([for(i=[0:4])[sin(72*i),cos(72*i)]],5);
790 circ = circle($fn=5,r=2.2);
791 assert_approx(reindex_polygon(circ,pent), [[0.951056516295,0.309016994375],[0.587785252292,-0.809016994375],[-0.587785252292,-0.809016994375],[-0.951056516295,0.309016994375],[0,1]]);
792 poly = [[-1,1],[-1,-1],[1,-1],[1,1],[0,0]];
793 ref = [for(i=[0:4])[sin(72*i),cos(72*i)]];
794 assert_approx(reindex_polygon(ref,poly),[[0,0],[1,1],[1,-1],[-1,-1],[-1,1]]);
795}
796*test_reindex_polygon();
797
798
799module test_align_polygon() {
800 // These tests fail because align_polygon displays output
801 /*
802 ellipse = yscale(3,circle(r=10, $fn=32));
803 tri = move([-50/3,-9],
804 subdivide_path([[0,0], [50,0], [0,27]], 32));
805 aligned = align_polygon(ellipse,tri, [0:5:180]);
806 assert_approx(aligned,
807 [[8.6933324366, 2.32937140592], [9.77174512453,
808 -1.69531953695], [10.8501578125, -5.72001047982],
809 [11.9285705004, -9.74470142269], [13.0069831883,
810 -13.7693923656], [9.28126928691, -14.7676943967],
811 [5.55555538551, -15.7659964278], [1.82984148411,
812 -16.7642984589], [-1.89587241729, -17.76260049],
813 [-5.62158631869, -18.7609025211], [-9.34730022009,
814 -19.7592045522], [-13.0730141215, -20.7575065833],
815 [-12.0623183481, -16.5048600039], [-11.0516225746,
816 -12.2522134245], [-10.0409268012, -7.99956684512],
817 [-9.03023102775, -3.74692026572], [-8.01953525431,
818 0.505726313678], [-7.00883948087, 4.75837289308],
819 [-5.99814370744, 9.01101947248], [-4.987447934,
820 13.2636660519], [-3.97675216056, 17.5163126313],
821 [-2.96605638713, 21.7689592107], [-1.95536061369,
822 26.0216057901], [-0.944664840253, 30.2742523695],
823 [0.0660309331843, 34.5268989489], [1.14444362111,
824 30.502208006], [2.22285630904, 26.4775170631],
825 [3.30126899697, 22.4528261203], [4.37968168489,
826 18.4281351774], [5.45809437282, 14.4034442345],
827 [6.53650706075, 10.3787532917], [7.61491974867,
828 6.35406234879]]);
829 ellipse2 = yscale(2,circle(r=10, $fn=32));
830 tri2 = subdivide_path([[0,0], [27,0], [-7,50]], 32);
831 T = [for(x=[-10:0], y=[-30:-15]) move([x,y])];
832 aligned2 = align_polygon(ellipse2,tri2, trans=T);
833 assert_approx(aligned2,
834 [[10.5384615385, -3.61538461538], [13.1538461538,
835 -7.46153846154], [15.7692307692, -11.3076923077],
836 [18.3846153846, -15.1538461538], [21, -19],
837 [17.1428571429, -19], [13.2857142857, -19],
838 [9.42857142857, -19], [5.57142857143, -19],
839 [1.71428571429, -19], [-2.14285714286, -19], [-6, -19],
840 [-6.58333333333, -14.8333333333], [-7.16666666667,
841 -10.6666666667], [-7.75, -6.5], [-8.33333333333,
842 -2.33333333333], [-8.91666666667, 1.83333333333], [-9.5,
843 6], [-10.0833333333, 10.1666666667], [-10.6666666667,
844 14.3333333333], [-11.25, 18.5], [-11.8333333333,
845 22.6666666667], [-12.4166666667, 26.8333333333], [-13,
846 31], [-10.3846153846, 27.1538461538], [-7.76923076923,
847 23.3076923077], [-5.15384615385, 19.4615384615],
848 [-2.53846153846, 15.6153846154], [0.0769230769231,
849 11.7692307692], [2.69230769231, 7.92307692308],
850 [5.30769230769, 4.07692307692], [7.92307692308,
851 0.230769230769]]);
852 */
853}
854*test_align_polygon();
855
856
857module test__noncollinear_triple() {
858 assert(_noncollinear_triple([[1,1],[2,2],[3,3],[4,4],[4,5],[5,6]]) == [0,5,3]);
859 assert(_noncollinear_triple([[1,1],[2,2],[8,3],[4,4],[4,5],[5,6]]) == [0,2,5]);
860 u = unit([5,3]);
861 assert_equal(_noncollinear_triple([for(i = [2,3,4,5,7,12,15]) i * u], error=false),[]);
862}
863*test__noncollinear_triple();
864
865
866module test_centroid() {
867 // polygons
868 $fn = 24;
869 assert_approx(centroid(circle(d=100)), [0,0]);
870 assert_approx(centroid(rect([40,60],rounding=10,anchor=LEFT)), [20,0]);
871 assert_approx(centroid(rect([40,60],rounding=10,anchor=FWD)), [0,30]);
872 poly = move([1,2.5,3.1],p=rot([12,49,24], p=path3d(circle(10,$fn=33))));
873 assert_approx(centroid(poly), [1,2.5,3.1]);
874
875 // regions
876 R = [square(10), move([5,4],circle(r=3,$fn=32)), right(15,square(7)), move([18,3],circle(r=2,$fn=5))];
877 assert_approx(centroid(R), [9.82836532809, 4.76313546433]);
878
879 // VNFs
880 assert_approx(centroid(cube(100, center=false)), [50,50,50]);
881 assert_approx(centroid(cube(100, center=true)), [0,0,0]);
882 assert_approx(centroid(cube(100, anchor=[1,1,1])), [-50,-50,-50]);
883 assert_approx(centroid(cube(100, anchor=BOT)), [0,0,50]);
884 assert_approx(centroid(cube(100, anchor=TOP)), [0,0,-50]);
885 assert_approx(centroid(sphere(d=100, anchor=CENTER, $fn=36)), [0,0,0]);
886 assert_approx(centroid(sphere(d=100, anchor=BOT, $fn=36)), [0,0,50]);
887 ellipse = xscale(2, p=circle($fn=24, r=3));
888 assert_approx(centroid(path_sweep(pentagon(r=1), path3d(ellipse), closed=true)),[0,0,0]);
889}
890*test_centroid();
891
892
893
894
895module test_point_in_polygon() {
896 poly = [for (a=[0:30:359]) 10*[cos(a),sin(a)]];
897 poly2 = [ [-3,-3],[2,-3],[2,1],[-1,1],[-1,-1],[1,-1],[1,2],[-3,2] ];
898 assert(point_in_polygon([0,0], poly) == 1);
899 assert(point_in_polygon([20,0], poly) == -1);
900 assert(point_in_polygon([20,0], poly,nonzero=false) == -1);
901 assert(point_in_polygon([5,5], poly) == 1);
902 assert(point_in_polygon([-5,5], poly) == 1);
903 assert(point_in_polygon([-5,-5], poly) == 1);
904 assert(point_in_polygon([5,-5], poly) == 1);
905 assert(point_in_polygon([5,-5], poly,nonzero=false,eps=EPSILON) == 1);
906 assert(point_in_polygon([-10,-10], poly) == -1);
907 assert(point_in_polygon([10,0], poly) == 0);
908 assert(point_in_polygon([0,10], poly) == 0);
909 assert(point_in_polygon([0,-10], poly) == 0);
910 assert(point_in_polygon([0,-10], poly,nonzero=false) == 0);
911 assert(point_in_polygon([0,0], poly2,nonzero=true) == 1);
912 assert(point_in_polygon([0,1], poly2,nonzero=true) == 0);
913 assert(point_in_polygon([0,1], poly2,nonzero=false) == 0);
914 assert(point_in_polygon([1,0], poly2,nonzero=false) == 0);
915 assert(point_in_polygon([0,0], poly2,nonzero=false,eps=EPSILON) == -1);
916}
917*test_point_in_polygon();
918
919
920
921module test_is_polygon_clockwise() {
922 assert(is_polygon_clockwise([[-1,1],[1,1],[1,-1],[-1,-1]]));
923 assert(!is_polygon_clockwise([[1,1],[-1,1],[-1,-1],[1,-1]]));
924 assert(is_polygon_clockwise(circle(d=100)));
925 assert(is_polygon_clockwise(square(100)));
926}
927*test_is_polygon_clockwise();
928
929
930module test_clockwise_polygon() {
931 path = circle(d=100);
932 rpath = concat([path[0]], reverse(select(path,1,-1)));
933 assert(clockwise_polygon(path) == path);
934 assert(clockwise_polygon(rpath) == path);
935}
936*test_clockwise_polygon();
937
938
939module test_ccw_polygon() {
940 path = circle(d=100);
941 rpath = concat([path[0]], reverse(select(path,1,-1)));
942 assert(ccw_polygon(path) == rpath);
943 assert(ccw_polygon(rpath) == rpath);
944}
945*test_ccw_polygon();
946
947
948module test_reverse_polygon() {
949 path = circle(d=100);
950 rpath = concat([path[0]], reverse(select(path,1,-1)));
951 assert(reverse_polygon(path) == rpath);
952 assert(reverse_polygon(rpath) == path);
953}
954*test_reverse_polygon();
955
956
957module test_convex_distance() {
958// 2D
959 c1 = circle(10,$fn=24);
960 c2 = move([15,0], p=c1);
961 assert(convex_distance(c1, c2)==0);
962 c3 = move([22,0],c1);
963 assert_approx(convex_distance(c1, c3),2);
964// 3D
965 s1 = sphere(10,$fn=4);
966 s2 = move([15,0], p=s1);
967 assert_approx(convex_distance(s1[0], s2[0]), 0.857864376269);
968 s3 = move([25.3,0],s1);
969 assert_approx(convex_distance(s1[0], s3[0]), 11.1578643763);
970 s4 = move([30,25],s1);
971 assert_approx(convex_distance(s1[0], s4[0]), 28.8908729653);
972 s5 = move([10*sqrt(2),0],s1);
973 assert_approx(convex_distance(s1[0], s5[0]), 0);
974}
975*test_convex_distance();
976
977module test_convex_collision() {
978// 2D
979 c1 = circle(10,$fn=24);
980 c2 = move([15,0], p=c1);
981 assert(convex_collision(c1, c2));
982 c3 = move([22,0],c1);
983 assert(!convex_collision(c1, c3));
984// 3D
985 s1 = sphere(10,$fn=4);
986 s2 = move([15,0], p=s1);
987 assert(!convex_collision(s1[0], s2[0]));
988 s3 = move([25.3,0],s1);
989 assert(!convex_collision(s1[0], s3[0]));
990 s4 = move([5,0],s1);
991 assert(convex_collision(s1[0], s4[0]));
992 s5 = move([10*sqrt(2),0],s1);
993 assert(convex_collision(s1[0], s5[0]));
994}
995*test_convex_distance();
996
997
998
999module test_rot_decode() {
1000 Tlist = [
1001 rot(37),
1002 xrot(49),
1003 yrot(88),
1004 rot(37,v=[1,3,3]),
1005 rot(41,v=[2,-3,4]),
1006 rot(180),
1007 xrot(180),
1008 yrot(180),
1009 rot(180, v=[3,2,-5], cp=[3,5,18]),
1010 rot(0.1, v=[1,2,3]),
1011 rot(-47,v=[3,4,5],cp=[9,3,4]),
1012 rot(197,v=[13,4,5],cp=[9,-3,4]),
1013 move([3,4,5]),
1014 move([3,4,5]) * rot(a=56, v=[5,3,-3], cp=[2,3,4]),
1015 ident(4)
1016 ];
1017 errlist = [for(T = Tlist)
1018 let(
1019 parm = rot_decode(T),
1020 restore = move(parm[3])*rot(a=parm[0],v=parm[1],cp=parm[2])
1021 )
1022 norm_fro(restore-T)];
1023 assert(max(errlist)<1e-13);
1024}
1025*test_rot_decode();
1026
1027
1028function standard_faces(faces) =
1029 sort([for(face=faces)
1030 list_rotate(face, min_index(face))]);
1031
1032module test_hull() {
1033 assert_equal(hull([[3,4],[5,5]]), [0,1]);
1034 assert_equal(hull([[3,4,1],[5,5,3]]), [0,1]);
1035
1036 test_collinear_2d = let(u = unit([5,3])) [ for(i = [9,2,3,4,5,7,12,15,13]) i * u ];
1037 assert_equal(sort(hull(test_collinear_2d)), [1,7]);
1038 test_collinear_3d = let(u = unit([5,3,2])) [ for(i = [9,2,3,4,5,7,12,15,13]) i * u ];
1039 assert_equal(sort(hull(test_collinear_3d)), [1,7]);
1040
1041 /* // produces some extra points along edges
1042 test_square_2d = [for(x=[1:5], y=[2:6]) [x,y]];
1043 echo(test_square_2d);
1044 move_copies(test_square_2d) circle(r=.1,$fn=16);
1045 color("red")move_copies(select(test_square_2d,hull(test_square_2d))) circle(r=.1,$fn=16);
1046 */
1047
1048 /* // also produces extra points along edges
1049 test_square_2d = rot(22,p=[for(x=[1:5], y=[2:6]) [x,y]]);
1050 echo(test_square_2d);
1051 move_copies(test_square_2d) circle(r=.1,$fn=16);
1052 color("red")move_copies(select(test_square_2d,hull(test_square_2d))) circle(r=.1,$fn=16);
1053 */
1054
1055 rand10_2d = [[1.55356, -1.98965], [4.23157, -0.947788], [-4.06193, -1.55463],
1056 [1.23889, -3.73133], [-1.02637, -4.0155], [4.26806, -4.61909],
1057 [3.59556, -3.1574], [-2.77776, -4.21857], [-3.66253,-4.34458], [1.82324, 0.102025]];
1058 assert_equal(sort(hull(rand10_2d)), [1,2,5,8,9]);
1059
1060 rand75_2d = [[-3.14743, -3.28139], [0.15343, -0.370249], [0.082565, 3.95939], [-2.56925, -3.16262], [-1.59463, 4.20893],
1061 [-4.90744, -1.21374], [-1.0819, -1.93703], [-3.72723, -3.0744], [-3.34339, 1.53535], [3.15803, -0.307388], [4.23289,
1062 4.46259], [1.73624, 1.38918], [3.72087, -1.55028], [1.2604, 2.30502], [-0.966431, 1.673], [-3.26866, -0.531443], [1.52605,
1063 0.991804], [-1.26305, 1.0737], [-4.31943, 4.11932], [0.488101, 0.0425981], [1.0233, -0.723037], [-4.73406, 2.14568],
1064 [-4.75915, 3.83262], [4.90999, -2.76668], [1.91971, -3.8604], [4.38594, -0.761767], [-0.352984, 1.55291], [2.02714,
1065 -0.340099], [1.76052, 2.09196], [-1.27485, -4.39477], [4.36364, 3.84964], [0.593612, -4.00028], [3.06833, -3.67117],
1066 [4.26834, -4.21213], [4.60226, -0.120432], [-2.45646, 2.60327], [-4.79461, 3.83724], [-3.29755, 0.760159], [0.218423,
1067 4.1687], [-0.115829, -2.06242], [-3.96188, 3.21568], [4.3018, -2.5299], [-4.41694, 4.75173], [-3.8393, 2.82212], [-1.14268,
1068 1.80751], [2.05805, 1.68593], [-3.0159, -2.91139], [-1.44828, -1.93564], [-0.265887, 0.519893], [-0.457361, -0.610096],
1069 [-0.426359, -2.37315], [-3.1018, 2.31141], [0.179141, -3.56242], [-0.491786, 0.813055], [-3.28502, -1.18933], [0.0914813,
1070 2.16122], [4.5777, 4.83972], [-1.07096, 2.74992], [-0.698689, 3.9032], [-1.21809, -1.54434], [3.14457, 4.92302], [-4.63176,
1071 2.81952], [4.84414, 4.63699], [2.4259, -0.747268], [-1.52088, -4.58305], [1.6961, -3.73678], [-0.483003, -3.67283],
1072 [-3.72746, -0.284265], [2.07629, 1.99902], [-3.12698, -0.96353], [4.02254, 3.41521], [-0.963391, -3.2143], [0.315255,
1073 0.593049], [1.57006, 1.80436], [4.60957, -2.86325]];
1074 assert_equal(sort(hull(rand75_2d)),[5,7,23,33,36,42,56,60,62,64]);
1075
1076 rand10_2d_rot = rot([22,44,12], p=path3d(rand10_2d));
1077 assert_equal(sort(hull(rand10_2d_rot)), [1,2,5,8,9]);
1078
1079 rand75_2d_rot = rot([122,-44,32], p=path3d(rand75_2d));
1080 assert_equal(sort(hull(rand75_2d_rot)), [5,7,23,33,36,42,56,60,62,64]);
1081
1082 testpoints_on_sphere = [ for(p =
1083 [
1084 [1,PHI,0], [-1,PHI,0], [1,-PHI,0], [-1,-PHI,0],
1085 [0,1,PHI], [0,-1,PHI], [0,1,-PHI], [0,-1,-PHI],
1086 [PHI,0,1], [-PHI,0,1], [PHI,0,-1], [-PHI,0,-1]
1087 ])
1088 unit(p)
1089 ];
1090 assert_equal(standard_faces(hull(testpoints_on_sphere)),
1091 standard_faces([[8, 4, 0], [0, 4, 1], [4, 8, 5], [8, 2, 5], [2, 3, 5], [0, 1, 6], [3, 2, 7], [1, 4, 9], [4, 5, 9],
1092 [5, 3, 9], [8, 0, 10], [2, 8, 10], [0, 6, 10], [6, 7, 10], [7, 2, 10], [6, 1, 11], [3, 7, 11], [7, 6, 11], [1, 9, 11], [9, 3, 11]]));
1093
1094 rand10_3d = [[14.0893, -15.2751, 21.0843], [-14.1564, 17.5751, 3.32094], [17.4966, 12.1717, 18.0607], [24.5489, 9.64591, 10.4738], [-12.0233, -24.4368, 13.1614],
1095 [6.24019, -18.4135, 24.9554], [11.9438, -15.9724, -22.6454], [11.6147, 7.56059, 7.5667], [-19.7491, 9.42769, 15.3419], [-10.3726, 16.3559, 3.38503]];
1096 assert_equal(standard_faces(hull(rand10_3d)),
1097 standard_faces([[3, 6, 0], [1, 3, 2], [3, 0, 2], [6, 1, 4], [0, 6, 5], [6, 4, 5], [2, 0, 5], [1, 2, 8], [2, 5, 8], [4, 1, 8], [5, 4, 8], [6, 3, 9], [3, 1, 9], [1, 6, 9]]));
1098
1099 rand25_3d = [[-20.5261, 14.5058, -11.6349], [16.4625, 20.1316, 12.9816], [-14.0268, 5.58802, 17.686], [-5.47944, 16.2501,
1100 5.3086], [20.2168, -11.8466, 12.4598], [14.4633, -15.1479, 4.82151], [12.7897, 5.25704, 19.6205], [11.2456,
1101 18.2794, -3.47074], [-1.87665, 22.9852, 1.99367], [-15.6052, -2.11009, 14.0096], [-10.7389, -14.569,
1102 5.6121], [24.5965, 17.9039, 20.8313], [-13.7054, 13.3362, 1.50374], [10.1111, -23.1494, 19.9305], [14.154,
1103 19.6682, -0.170182], [-22.6438, 22.7429, -0.776773], [-9.75056, 17.8896, -8.04152], [23.1746, 20.5475,
1104 22.6957], [-10.5356, -4.32407, -7.0911], [2.20779, -8.30749, 6.87185], [23.2643, 2.64462, -19.0087],
1105 [24.4055, 24.4504, 23.4777], [-3.84086, -6.98473, -10.2889], [0.178043, -16.07, 16.8081], [-8.86482,
1106 -12.8256, 14.7418], [11.1759, -11.5614, -11.643], [7.16751, 13.9344, -19.1675], [2.26602, -10.5374,
1107 0.125718], [-13.9053, 11.1143, -21.9289], [24.9018, -23.5307, -21.4684], [-13.6609, -19.6495, -8.91583],
1108 [-16.5393, -22.4105, -6.91617], [-4.11378, -3.14362, -5.6881], [7.50883, -17.5284, -0.0615319], [-7.41739,
1109 0.0721313, -7.47111], [22.6975, -7.99655, 14.0555], [-13.3644, 9.26993, 20.858], [-13.6889, 16.7462,
1110 -14.5836], [16.5137, 3.90703, -5.49396], [-6.75614, -11.1444, -24.5309], [22.9868, 10.0028, 12.2866],
1111 [-4.81079, -0.967785, -10.4726], [-0.949023, 23.1441, -2.08208], [16.1256, -8.2295, -24.0113], [6.45274,
1112 -7.21416, 23.1409], [22.8274, 1.07038, 19.1756], [-10.6256, -10.0112, -6.12274], [6.29254, -7.81875,
1113 -24.4037], [22.8538, 8.78163, -6.82567], [-1.96142, 19.1728, -1.726]];
1114 assert_equal(sort(hull(rand25_3d)),sort([[21, 29, 11], [29, 21, 20], [21, 14, 20], [20, 14, 26], [15, 0, 28], [13, 29, 31], [0, 15,
1115 31], [15, 9, 31], [9, 24, 31], [24, 13, 31], [28, 0, 31], [11, 29, 35], [29, 13, 35], [15,
1116 21, 36], [9, 15, 36], [24, 9, 36], [13, 24, 36], [15, 28, 37], [28, 26, 37], [28, 31, 39],
1117 [31, 29, 39], [14, 21, 42], [21, 15, 42], [26, 14, 42], [15, 37, 42], [37, 26, 42], [29, 20,
1118 43], [39, 29, 43], [20, 26, 43], [26, 28, 43], [21, 13, 44], [13, 36, 44], [36, 21, 44],
1119 [21, 11, 45], [11, 35, 45], [13, 21, 45], [35, 13, 45], [28, 39, 47], [39, 43, 47], [43, 28, 47]]));
1120
1121 /* // Inconsistently treats coplanar faces: sometimes face center vertex is included in output, sometimes not
1122 test_cube_3d = [for(x=[1:3], y=[1:3], z=[1:3]) [x,y,z]];
1123 assert_equal(hull(test_cube_3d), [[3, 2, 0], [2, 3, 4], [26, 2, 5], [2, 4, 5], [4, 3, 6], [5, 4, 6], [5, 6, 7], [6, 26, 7], [26, 5, 8],
1124 [5, 7, 8], [7, 26, 8], [0, 2, 9], [3, 0, 9], [6, 3, 9], [9, 2, 10], [2, 26, 11], [10, 2, 11], [6, 9, 12],
1125 [26, 6, 15], [6, 12, 15], [9, 10, 18], [10, 11, 18], [12, 9, 18], [15, 12, 18], [26, 18, 19], [18, 11, 19],
1126 [11, 26, 20], [26, 19, 20], [19, 11, 20], [15, 18, 21], [18, 26, 21], [26, 15, 24], [15, 21, 24], [21, 26, 24]]);
1127 echo(len=len(hull(test_cube_3d)));
1128 */
1129}
1130test_hull();
1131
1132
1133module test_hull2d_path() {
1134 assert_equal(hull([[3,4],[5,5]]), [0,1]);
1135 assert_equal(hull([[3,4,1],[5,5,3]]), [0,1]);
1136
1137 test_collinear_2d = let(u = unit([5,3])) [ for(i = [9,2,3,4,5,7,12,15,13]) i * u ];
1138 assert_equal(sort(hull(test_collinear_2d)), [1,7]);
1139 test_collinear_3d = let(u = unit([5,3,2])) [ for(i = [9,2,3,4,5,7,12,15,13]) i * u ];
1140 assert_equal(sort(hull(test_collinear_3d)), [1,7]);
1141
1142 rand10_2d = [[1.55356, -1.98965], [4.23157, -0.947788], [-4.06193, -1.55463],
1143 [1.23889, -3.73133], [-1.02637, -4.0155], [4.26806, -4.61909],
1144 [3.59556, -3.1574], [-2.77776, -4.21857], [-3.66253,-4.34458], [1.82324, 0.102025]];
1145 assert_equal(sort(hull(rand10_2d)), [1,2,5,8,9]);
1146
1147 rand75_2d = [[-3.14743, -3.28139], [0.15343, -0.370249], [0.082565, 3.95939], [-2.56925, -3.16262], [-1.59463, 4.20893],
1148 [-4.90744, -1.21374], [-1.0819, -1.93703], [-3.72723, -3.0744], [-3.34339, 1.53535], [3.15803, -0.307388], [4.23289,
1149 4.46259], [1.73624, 1.38918], [3.72087, -1.55028], [1.2604, 2.30502], [-0.966431, 1.673], [-3.26866, -0.531443], [1.52605,
1150 0.991804], [-1.26305, 1.0737], [-4.31943, 4.11932], [0.488101, 0.0425981], [1.0233, -0.723037], [-4.73406, 2.14568],
1151 [-4.75915, 3.83262], [4.90999, -2.76668], [1.91971, -3.8604], [4.38594, -0.761767], [-0.352984, 1.55291], [2.02714,
1152 -0.340099], [1.76052, 2.09196], [-1.27485, -4.39477], [4.36364, 3.84964], [0.593612, -4.00028], [3.06833, -3.67117],
1153 [4.26834, -4.21213], [4.60226, -0.120432], [-2.45646, 2.60327], [-4.79461, 3.83724], [-3.29755, 0.760159], [0.218423,
1154 4.1687], [-0.115829, -2.06242], [-3.96188, 3.21568], [4.3018, -2.5299], [-4.41694, 4.75173], [-3.8393, 2.82212], [-1.14268,
1155 1.80751], [2.05805, 1.68593], [-3.0159, -2.91139], [-1.44828, -1.93564], [-0.265887, 0.519893], [-0.457361, -0.610096],
1156 [-0.426359, -2.37315], [-3.1018, 2.31141], [0.179141, -3.56242], [-0.491786, 0.813055], [-3.28502, -1.18933], [0.0914813,
1157 2.16122], [4.5777, 4.83972], [-1.07096, 2.74992], [-0.698689, 3.9032], [-1.21809, -1.54434], [3.14457, 4.92302], [-4.63176,
1158 2.81952], [4.84414, 4.63699], [2.4259, -0.747268], [-1.52088, -4.58305], [1.6961, -3.73678], [-0.483003, -3.67283],
1159 [-3.72746, -0.284265], [2.07629, 1.99902], [-3.12698, -0.96353], [4.02254, 3.41521], [-0.963391, -3.2143], [0.315255,
1160 0.593049], [1.57006, 1.80436], [4.60957, -2.86325]];
1161 assert_equal(sort(hull(rand75_2d)),[5,7,23,33,36,42,56,60,62,64]);
1162
1163 rand10_2d_rot = rot([22,44,12], p=path3d(rand10_2d));
1164 assert_equal(sort(hull(rand10_2d_rot)), [1,2,5,8,9]);
1165
1166 rand75_2d_rot = rot([122,-44,32], p=path3d(rand75_2d));
1167 assert_equal(sort(hull(rand75_2d_rot)), [5,7,23,33,36,42,56,60,62,64]);
1168}
1169test_hull2d_path();
1170
1171
1172module test_hull3d_faces() {
1173 testpoints_on_sphere = [ for(p =
1174 [
1175 [1,PHI,0], [-1,PHI,0], [1,-PHI,0], [-1,-PHI,0],
1176 [0,1,PHI], [0,-1,PHI], [0,1,-PHI], [0,-1,-PHI],
1177 [PHI,0,1], [-PHI,0,1], [PHI,0,-1], [-PHI,0,-1]
1178 ])
1179 unit(p)
1180 ];
1181 assert_equal(standard_faces(hull(testpoints_on_sphere)),
1182 standard_faces([[8, 4, 0], [0, 4, 1], [4, 8, 5], [8, 2, 5], [2, 3, 5], [0, 1, 6], [3, 2, 7], [1, 4, 9], [4, 5, 9],
1183 [5, 3, 9], [8, 0, 10], [2, 8, 10], [0, 6, 10], [6, 7, 10], [7, 2, 10], [6, 1, 11], [3, 7, 11], [7, 6, 11], [1, 9, 11], [9, 3, 11]]));
1184
1185 rand10_3d = [[14.0893, -15.2751, 21.0843], [-14.1564, 17.5751, 3.32094], [17.4966, 12.1717, 18.0607], [24.5489, 9.64591, 10.4738], [-12.0233, -24.4368, 13.1614],
1186 [6.24019, -18.4135, 24.9554], [11.9438, -15.9724, -22.6454], [11.6147, 7.56059, 7.5667], [-19.7491, 9.42769, 15.3419], [-10.3726, 16.3559, 3.38503]];
1187 assert_equal(standard_faces(hull(rand10_3d)),
1188 standard_faces([[3, 6, 0], [1, 3, 2], [3, 0, 2], [6, 1, 4], [0, 6, 5], [6, 4, 5], [2, 0, 5], [1, 2, 8], [2, 5, 8], [4, 1, 8], [5, 4, 8], [6, 3, 9], [3, 1, 9], [1, 6, 9]]));
1189
1190 rand25_3d = [[-20.5261, 14.5058, -11.6349], [16.4625, 20.1316, 12.9816], [-14.0268, 5.58802, 17.686], [-5.47944, 16.2501,
1191 5.3086], [20.2168, -11.8466, 12.4598], [14.4633, -15.1479, 4.82151], [12.7897, 5.25704, 19.6205], [11.2456,
1192 18.2794, -3.47074], [-1.87665, 22.9852, 1.99367], [-15.6052, -2.11009, 14.0096], [-10.7389, -14.569,
1193 5.6121], [24.5965, 17.9039, 20.8313], [-13.7054, 13.3362, 1.50374], [10.1111, -23.1494, 19.9305], [14.154,
1194 19.6682, -0.170182], [-22.6438, 22.7429, -0.776773], [-9.75056, 17.8896, -8.04152], [23.1746, 20.5475,
1195 22.6957], [-10.5356, -4.32407, -7.0911], [2.20779, -8.30749, 6.87185], [23.2643, 2.64462, -19.0087],
1196 [24.4055, 24.4504, 23.4777], [-3.84086, -6.98473, -10.2889], [0.178043, -16.07, 16.8081], [-8.86482,
1197 -12.8256, 14.7418], [11.1759, -11.5614, -11.643], [7.16751, 13.9344, -19.1675], [2.26602, -10.5374,
1198 0.125718], [-13.9053, 11.1143, -21.9289], [24.9018, -23.5307, -21.4684], [-13.6609, -19.6495, -8.91583],
1199 [-16.5393, -22.4105, -6.91617], [-4.11378, -3.14362, -5.6881], [7.50883, -17.5284, -0.0615319], [-7.41739,
1200 0.0721313, -7.47111], [22.6975, -7.99655, 14.0555], [-13.3644, 9.26993, 20.858], [-13.6889, 16.7462,
1201 -14.5836], [16.5137, 3.90703, -5.49396], [-6.75614, -11.1444, -24.5309], [22.9868, 10.0028, 12.2866],
1202 [-4.81079, -0.967785, -10.4726], [-0.949023, 23.1441, -2.08208], [16.1256, -8.2295, -24.0113], [6.45274,
1203 -7.21416, 23.1409], [22.8274, 1.07038, 19.1756], [-10.6256, -10.0112, -6.12274], [6.29254, -7.81875,
1204 -24.4037], [22.8538, 8.78163, -6.82567], [-1.96142, 19.1728, -1.726]];
1205 assert_equal(sort(hull(rand25_3d)), sort([[21, 29, 11], [29, 21, 20], [21, 14, 20], [20, 14, 26], [15, 0, 28], [13, 29, 31], [0, 15,
1206 31], [15, 9, 31], [9, 24, 31], [24, 13, 31], [28, 0, 31], [11, 29, 35], [29, 13, 35], [15,
1207 21, 36], [9, 15, 36], [24, 9, 36], [13, 24, 36], [15, 28, 37], [28, 26, 37], [28, 31, 39],
1208 [31, 29, 39], [14, 21, 42], [21, 15, 42], [26, 14, 42], [15, 37, 42], [37, 26, 42], [29, 20,
1209 43], [39, 29, 43], [20, 26, 43], [26, 28, 43], [21, 13, 44], [13, 36, 44], [36, 21, 44],
1210 [21, 11, 45], [11, 35, 45], [13, 21, 45], [35, 13, 45], [28, 39, 47], [39, 43, 47], [43, 28, 47]]));
1211}
1212test_hull3d_faces();
1213
1214
1215
1216// vim: expandtab tabstop=4 shiftwidth=4 softtabstop=4 nowrap